package Simple3;

import java.util.ArrayList;

public class tel_combination {

	 public static String[] dic ={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
	    
	    public static ArrayList<String> letterCombinations(String digits) {
	        // IMPORTANT: Please reset any member data you declared, as
	        // the same Solution instance will be reused for each test case.
	        ArrayList<String> ret = new ArrayList<String>();
	        helper(digits,"",0,digits.length(),ret);
	        return ret;        
	    }
	    
	    public static void helper(String digits, String s, int pos, int n, ArrayList<String> ret){
	        if(pos==n){
	            ret.add(s);
	            return;
	        }
	        int num = Integer.parseInt(String.valueOf(digits.charAt(pos)))-0;
	        for(int i=0;i<dic[num].length();++i){
	            String temp = s;
	            temp = temp + dic[num].charAt(i);
	            helper(digits,temp,pos+1,n,ret);
	        }
	    }
	    
	    public static ArrayList<String> letterCom_nonrecursive(String digits){
	    	ArrayList<String> ret = new ArrayList<>();
	    	ret.add("");
	    	for(int i=0;i<digits.length();++i){
	    		String s = dic[digits.charAt(i)-'0'];
	    		ArrayList<String> temp = new ArrayList<>();
	    		for(int j=0;j<s.length();++j){
	    			for(int k=0;k<ret.size();++k){
	    				temp.add(ret.get(k)+String.valueOf(s.charAt(j)));
	    			}
	    		}
	    		ret=temp;
	    	}
	    	return ret;
	    }
	    
	public static void main(String[] args) {
		// TODO Auto-generated method stub

//		ArrayList<String> test = letterCombinations("234");
		ArrayList<String> test = letterCom_nonrecursive("23");
		for(int i=0;i<test.size();++i)
			System.out.print(test.get(i)+", ");
	}

}
